package LeetCode.month01.day30;

import java.util.Arrays;

public class No1838 {
    public static void main(String[] args) {
        System.out.println(maxFrequency(new int[]{1,4,8,13},5));
    }
    public static int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long sum = 0;
        int res = 1;
        int left = 0;
        for (int i = 1; i < n; i++) {
            sum+=(long)(nums[i]-nums[i-1])*(i-left);
            while(sum>k){
                sum-=nums[i]-nums[left];
                left++;
            }
            res = Math.max(res,i-left+1);
        }
        return res;
    }
}
